package Aleehot100;

/**
 * ClassName: c093
 * Package: Aleehot100
 * Description:5. 最长回文子串
 *
 * @Author BCXJ
 * @Create 2025/9/15 06:28
 * @Version 1.0
 * @Since 1.0
 */
public class c093 {
    public static void main(String[] args) {
        System.out.println(longestPalindrome("babad"));
    }


    public static String longestPalindrome(String s) {
        if(s == null || s.isEmpty()) return "";

        // 下标起始和结束
        int start = 0, end = 0;

        // 以i为中心进行扩散
        for (int i = 0; i < s.length(); i++) {
            // 奇数长度计算
            int len1 = expandAroundCenter(s, i, i);
            // 偶数长度计算
            int len2 = expandAroundCenter(s, i, i + 1);

            // 长度重新整合
            int maxLen = Math.max(len1, len2);
            if(end - start + 1 < maxLen) {
                start = i - (maxLen - 1) / 2;
                end = i + maxLen / 2;
            }
        }

        // 返回start , end + 1 的字符
        return s.substring(start, end + 1);
    }

    // 以l,r 为中心进行两边的扩散
    private static int expandAroundCenter(String s, int l, int r) {
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l --; r ++;
        }
        return r - l - 1;
    }
}
